package java.util;

/**
 * A basic implementation of most of the methods in the List interface to make
 * it easier to create a List based on a random-access data structure. If the
 * list is sequential (such as a linked list), use AbstractSequentialList. To
 * create an unmodifiable list, it is only necessary to override the size() and
 * get(int) methods (this contrasts with all other abstract collection classes
 * which require an iterator to be provided). To make the list modifiable, the
 * set(int, Object) method should also be overridden, and to make the list
 * resizable, the add(int, Object) and remove(int) methods should be overridden
 * too. Other methods should be overridden if the backing data structure allows
 * for a more efficient implementation. The precise implementation used by
 * AbstractList is documented, so that subclasses can tell which methods could
 * be implemented more efficiently.
 * <p>
 * 
 * As recommended by Collection and List, the subclass should provide at least a
 * no-argument and a Collection constructor. This class is not synchronized.
 * 
 * @author Original author unknown
 * @author Bryce McKinlay
 * @author Eric Blake (ebb9@email.byu.edu)
 * @see Collection
 * @see List
 * @see AbstractSequentialList
 * @see AbstractCollection
 * @see ListIterator
 * @since 1.2
 * @status updated to 1.4
 */
public abstract class AbstractList<E> extends AbstractCollection<E> implements
		List<E> {
	/**
	 * A count of the number of structural modifications that have been made to
	 * the list (that is, insertions and removals). Structural modifications are
	 * ones which change the list size or affect how iterations would behave.
	 * This field is available for use by Iterator and ListIterator, in order to
	 * throw a {@link ConcurrentModificationException} in response to the next
	 * operation on the iterator. This <i>fail-fast</i> behavior saves the user
	 * from many subtle bugs otherwise possible from concurrent modification
	 * during iteration.
	 * <p>
	 * 
	 * To make lists fail-fast, increment this field by just 1 in the
	 * <code>add(int, Object)</code> and <code>remove(int)</code> methods.
	 * Otherwise, this field may be ignored.
	 */
	protected transient int modCount;

	/**
	 * The main constructor, for use by subclasses.
	 */
	protected AbstractList() {
	}

	/**
	 * Returns the elements at the specified position in the list.
	 * 
	 * @param index
	 *            the element to return
	 * @return the element at that position
	 * @throws IndexOutOfBoundsException
	 *             if index &lt; 0 || index &gt;= size()
	 */
	public abstract E get(int index);

	/**
	 * Insert an element into the list at a given position (optional operation).
	 * This shifts all existing elements from that position to the end one index
	 * to the right. This version of add has no return, since it is assumed to
	 * always succeed if there is no exception. This implementation always
	 * throws UnsupportedOperationException, and must be overridden to make a
	 * modifiable List. If you want fail-fast iterators, be sure to increment
	 * modCount when overriding this.
	 * 
	 * @param index
	 *            the location to insert the item
	 * @param o
	 *            the object to insert
	 * @throws UnsupportedOperationException
	 *             if this list does not support the add operation
	 * @throws IndexOutOfBoundsException
	 *             if index &lt; 0 || index &gt; size()
	 * @throws ClassCastException
	 *             if o cannot be added to this list due to its type
	 * @throws IllegalArgumentException
	 *             if o cannot be added to this list for some other reason
	 * @see #modCount
	 */
	public void add(int index, E o) {
		throw new UnsupportedOperationException();
	}

	/**
	 * Add an element to the end of the list (optional operation). If the list
	 * imposes restraints on what can be inserted, such as no null elements,
	 * this should be documented. This implementation calls
	 * <code>add(size(), o);</code>, and will fail if that version does.
	 * 
	 * @param o
	 *            the object to add
	 * @return true, as defined by Collection for a modified list
	 * @throws UnsupportedOperationException
	 *             if this list does not support the add operation
	 * @throws ClassCastException
	 *             if o cannot be added to this list due to its type
	 * @throws IllegalArgumentException
	 *             if o cannot be added to this list for some other reason
	 * @see #add(int, Object)
	 */
	public boolean add(E o) {
		add(size(), o);
		return true;
	}

	/**
	 * Insert the contents of a collection into the list at a given position
	 * (optional operation). Shift all elements at that position to the right by
	 * the number of elements inserted. This operation is undefined if this list
	 * is modified during the operation (for example, if you try to insert a
	 * list into itself). This implementation uses the iterator of the
	 * collection, repeatedly calling add(int, Object); this will fail if add
	 * does. This can often be made more efficient.
	 * 
	 * @param index
	 *            the location to insert the collection
	 * @param c
	 *            the collection to insert
	 * @return true if the list was modified by this action, that is, if c is
	 *         non-empty
	 * @throws UnsupportedOperationException
	 *             if this list does not support the addAll operation
	 * @throws IndexOutOfBoundsException
	 *             if index &lt; 0 || index &gt; size()
	 * @throws ClassCastException
	 *             if some element of c cannot be added to this list due to its
	 *             type
	 * @throws IllegalArgumentException
	 *             if some element of c cannot be added to this list for some
	 *             other reason
	 * @throws NullPointerException
	 *             if the specified collection is null
	 * @see #add(int, Object)
	 */
	public boolean addAll(int index, Collection<? extends E> c) {
		Iterator<? extends E> itr = c.iterator();
		int size = c.size();
		for (int pos = size; pos > 0; pos--)
			add(index++, itr.next());
		return size > 0;
	}

	/**
	 * Clear the list, such that a subsequent call to isEmpty() would return
	 * true (optional operation). This implementation calls
	 * <code>removeRange(0, size())</code>, so it will fail unless remove or
	 * removeRange is overridden.
	 * 
	 * @throws UnsupportedOperationException
	 *             if this list does not support the clear operation
	 * @see #remove(int)
	 * @see #removeRange(int, int)
	 */
	public void clear() {
		removeRange(0, size());
	}

	/**
	 * Test whether this list is equal to another object. A List is defined to
	 * be equal to an object if and only if that object is also a List, and the
	 * two lists have the same sequence. Two lists l1 and l2 are equal if and
	 * only if <code>l1.size() == l2.size()</code>, and for every integer n
	 * between 0 and <code>l1.size() - 1</code> inclusive,
	 * <code>l1.get(n) == null ?
	 * l2.get(n) == null : l1.get(n).equals(l2.get(n))</code>.
	 * <p>
	 * 
	 * This implementation returns true if the object is this, or false if the
	 * object is not a List. Otherwise, it iterates over both lists (with
	 * iterator()), returning false if two elements compare false or one list is
	 * shorter, and true if the iteration completes successfully.
	 * 
	 * @param o
	 *            the object to test for equality with this list
	 * @return true if o is equal to this list
	 * @see Object#equals(Object)
	 * @see #hashCode()
	 */
	public boolean equals(Object o) {
		if (o == this)
			return true;
		if (!(o instanceof List))
			return false;
		int size = size();
		if (size != ((List<?>) o).size())
			return false;

		Iterator<E> itr1 = iterator();
		Iterator<?> itr2 = ((List<?>) o).iterator();

		while (--size >= 0)
			if (!equals(itr1.next(), itr2.next()))
				return false;
		return true;
	}

	/**
	 * Obtains a hash code for this list. In order to obey the general contract
	 * of the hashCode method of class Object, this value is calculated as
	 * follows:
	 * 
	 * <pre>
	 * hashCode = 1;
	 * Iterator i = list.iterator();
	 * while (i.hasNext()) {
	 * 	Object obj = i.next();
	 * 	hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
	 * }
	 * </pre>
	 * 
	 * This ensures that the general contract of Object.hashCode() is adhered
	 * to.
	 * 
	 * @return the hash code of this list
	 * 
	 * @see Object#hashCode()
	 * @see #equals(Object)
	 */
	public int hashCode() {
		int hashCode = 1;
		Iterator<E> itr = iterator();
		int pos = size();
		while (--pos >= 0)
			hashCode = 31 * hashCode + hashCode(itr.next());
		return hashCode;
	}

	/**
	 * Obtain the first index at which a given object is to be found in this
	 * list. This implementation follows a listIterator() until a match is
	 * found, or returns -1 if the list end is reached.
	 * 
	 * @param o
	 *            the object to search for
	 * @return the least integer n such that <code>o == null ? get(n) == null :
	 *         o.equals(get(n))</code>, or -1 if there is no such index
	 */
	public int indexOf(Object o) {
		ListIterator<E> itr = listIterator();
		int size = size();
		for (int pos = 0; pos < size; pos++)
			if (equals(o, itr.next()))
				return pos;
		return -1;
	}

	/**
	 * Obtain an Iterator over this list, whose sequence is the list order. This
	 * implementation uses size(), get(int), and remove(int) of the backing
	 * list, and does not support remove unless the list does. This
	 * implementation is fail-fast if you correctly maintain modCount. Also,
	 * this implementation is specified by Sun to be distinct from listIterator,
	 * although you could easily implement it as
	 * <code>return listIterator(0)</code>.
	 * 
	 * @return an Iterator over the elements of this list, in order
	 * @see #modCount
	 */
	public Iterator<E> iterator() {
		// Bah, Sun's implementation forbids using listIterator(0).
		return new Iterator<E>() {
			private int pos = 0;
			private int size = size();
			private int last = -1;
			private int knownMod = modCount;

			// This will get inlined, since it is private.
			/**
			 * Checks for modifications made to the list from elsewhere while
			 * iteration is in progress.
			 * 
			 * @throws ConcurrentModificationException
			 *             if the list has been modified elsewhere.
			 */
			private void checkMod() {
				if (knownMod != modCount)
					throw new ConcurrentModificationException();
			}

			/**
			 * Tests to see if there are any more objects to return.
			 * 
			 * @return True if the end of the list has not yet been reached.
			 */
			public boolean hasNext() {
				return pos < size;
			}

			/**
			 * Retrieves the next object from the list.
			 * 
			 * @return The next object.
			 * @throws NoSuchElementException
			 *             if there are no more objects to retrieve.
			 * @throws ConcurrentModificationException
			 *             if the list has been modified elsewhere.
			 */
			public E next() {
				checkMod();
				if (pos == size)
					throw new NoSuchElementException();
				last = pos;
				return get(pos++);
			}

			/**
			 * Removes the last object retrieved by <code>next()</code> from the
			 * list, if the list supports object removal.
			 * 
			 * @throws ConcurrentModificationException
			 *             if the list has been modified elsewhere.
			 * @throws IllegalStateException
			 *             if the iterator is positioned before the start of the
			 *             list or the last object has already been removed.
			 * @throws UnsupportedOperationException
			 *             if the list does not support removing elements.
			 */
			public void remove() {
				checkMod();
				if (last < 0)
					throw new IllegalStateException();
				AbstractList.this.remove(last);
				pos--;
				size--;
				last = -1;
				knownMod = modCount;
			}
		};
	}

	/**
	 * Obtain the last index at which a given object is to be found in this
	 * list. This implementation grabs listIterator(size()), then searches
	 * backwards for a match or returns -1.
	 * 
	 * @return the greatest integer n such that <code>o == null ? get(n) == null
	 *         : o.equals(get(n))</code>, or -1 if there is no such index
	 */
	public int lastIndexOf(Object o) {
		int pos = size();
		ListIterator<E> itr = listIterator(pos);
		while (--pos >= 0)
			if (equals(o, itr.previous()))
				return pos;
		return -1;
	}

	/**
	 * Obtain a ListIterator over this list, starting at the beginning. This
	 * implementation returns listIterator(0).
	 * 
	 * @return a ListIterator over the elements of this list, in order, starting
	 *         at the beginning
	 */
	public ListIterator<E> listIterator() {
		return listIterator(0);
	}

	/**
	 * Obtain a ListIterator over this list, starting at a given position. A
	 * first call to next() would return the same as get(index), and a first
	 * call to previous() would return the same as get(index - 1).
	 * <p>
	 * 
	 * This implementation uses size(), get(int), set(int, Object), add(int,
	 * Object), and remove(int) of the backing list, and does not support
	 * remove, set, or add unless the list does. This implementation is
	 * fail-fast if you correctly maintain modCount.
	 * 
	 * @param index
	 *            the position, between 0 and size() inclusive, to begin the
	 *            iteration from
	 * @return a ListIterator over the elements of this list, in order, starting
	 *         at index
	 * @throws IndexOutOfBoundsException
	 *             if index &lt; 0 || index &gt; size()
	 * @see #modCount
	 */
	public ListIterator<E> listIterator(final int index) {
		if (index < 0 || index > size())
			throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
					+ size());

		return new ListIterator<E>() {
			private int knownMod = modCount;
			private int position = index;
			private int lastReturned = -1;
			private int size = size();

			// This will get inlined, since it is private.
			/**
			 * Checks for modifications made to the list from elsewhere while
			 * iteration is in progress.
			 * 
			 * @throws ConcurrentModificationException
			 *             if the list has been modified elsewhere.
			 */
			private void checkMod() {
				if (knownMod != modCount)
					throw new ConcurrentModificationException();
			}

			/**
			 * Tests to see if there are any more objects to return.
			 * 
			 * @return True if the end of the list has not yet been reached.
			 */
			public boolean hasNext() {
				return position < size;
			}

			/**
			 * Tests to see if there are objects prior to the current position
			 * in the list.
			 * 
			 * @return True if objects exist prior to the current position of
			 *         the iterator.
			 */
			public boolean hasPrevious() {
				return position > 0;
			}

			/**
			 * Retrieves the next object from the list.
			 * 
			 * @return The next object.
			 * @throws NoSuchElementException
			 *             if there are no more objects to retrieve.
			 * @throws ConcurrentModificationException
			 *             if the list has been modified elsewhere.
			 */
			public E next() {
				checkMod();
				if (position == size)
					throw new NoSuchElementException();
				lastReturned = position;
				return get(position++);
			}

			/**
			 * Retrieves the previous object from the list.
			 * 
			 * @return The next object.
			 * @throws NoSuchElementException
			 *             if there are no previous objects to retrieve.
			 * @throws ConcurrentModificationException
			 *             if the list has been modified elsewhere.
			 */
			public E previous() {
				checkMod();
				if (position == 0)
					throw new NoSuchElementException();
				lastReturned = --position;
				return get(lastReturned);
			}

			/**
			 * Returns the index of the next element in the list, which will be
			 * retrieved by <code>next()</code>
			 * 
			 * @return The index of the next element.
			 */
			public int nextIndex() {
				return position;
			}

			/**
			 * Returns the index of the previous element in the list, which will
			 * be retrieved by <code>previous()</code>
			 * 
			 * @return The index of the previous element.
			 */
			public int previousIndex() {
				return position - 1;
			}

			/**
			 * Removes the last object retrieved by <code>next()</code> or
			 * <code>previous()</code> from the list, if the list supports
			 * object removal.
			 * 
			 * @throws IllegalStateException
			 *             if the iterator is positioned before the start of the
			 *             list or the last object has already been removed.
			 * @throws UnsupportedOperationException
			 *             if the list does not support removing elements.
			 * @throws ConcurrentModificationException
			 *             if the list has been modified elsewhere.
			 */
			public void remove() {
				checkMod();
				if (lastReturned < 0)
					throw new IllegalStateException();
				AbstractList.this.remove(lastReturned);
				size--;
				position = lastReturned;
				lastReturned = -1;
				knownMod = modCount;
			}

			/**
			 * Replaces the last object retrieved by <code>next()</code> or
			 * <code>previous</code> with o, if the list supports object
			 * replacement and an add or remove operation has not already been
			 * performed.
			 * 
			 * @throws IllegalStateException
			 *             if the iterator is positioned before the start of the
			 *             list or the last object has already been removed.
			 * @throws UnsupportedOperationException
			 *             if the list doesn't support the addition or removal
			 *             of elements.
			 * @throws ClassCastException
			 *             if the type of o is not a valid type for this list.
			 * @throws IllegalArgumentException
			 *             if something else related to o prevents its addition.
			 * @throws ConcurrentModificationException
			 *             if the list has been modified elsewhere.
			 */
			public void set(E o) {
				checkMod();
				if (lastReturned < 0)
					throw new IllegalStateException();
				AbstractList.this.set(lastReturned, o);
			}

			/**
			 * Adds the supplied object before the element that would be
			 * returned by a call to <code>next()</code>, if the list supports
			 * addition.
			 * 
			 * @param o
			 *            The object to add to the list.
			 * @throws UnsupportedOperationException
			 *             if the list doesn't support the addition of new
			 *             elements.
			 * @throws ClassCastException
			 *             if the type of o is not a valid type for this list.
			 * @throws IllegalArgumentException
			 *             if something else related to o prevents its addition.
			 * @throws ConcurrentModificationException
			 *             if the list has been modified elsewhere.
			 */
			public void add(E o) {
				checkMod();
				AbstractList.this.add(position++, o);
				size++;
				lastReturned = -1;
				knownMod = modCount;
			}
		};
	}

	/**
	 * Remove the element at a given position in this list (optional operation).
	 * Shifts all remaining elements to the left to fill the gap. This
	 * implementation always throws an UnsupportedOperationException. If you
	 * want fail-fast iterators, be sure to increment modCount when overriding
	 * this.
	 * 
	 * @param index
	 *            the position within the list of the object to remove
	 * @return the object that was removed
	 * @throws UnsupportedOperationException
	 *             if this list does not support the remove operation
	 * @throws IndexOutOfBoundsException
	 *             if index &lt; 0 || index &gt;= size()
	 * @see #modCount
	 */
	public E remove(int index) {
		throw new UnsupportedOperationException();
	}

	/**
	 * Remove a subsection of the list. This is called by the clear and
	 * removeRange methods of the class which implements subList, which are
	 * difficult for subclasses to override directly. Therefore, this method
	 * should be overridden instead by the more efficient implementation, if one
	 * exists. Overriding this can reduce quadratic efforts to constant time in
	 * some cases!
	 * <p>
	 * 
	 * This implementation first checks for illegal or out of range arguments.
	 * It then obtains a ListIterator over the list using
	 * listIterator(fromIndex). It then calls next() and remove() on this
	 * iterator repeatedly, toIndex - fromIndex times.
	 * 
	 * @param fromIndex
	 *            the index, inclusive, to remove from.
	 * @param toIndex
	 *            the index, exclusive, to remove to.
	 * @throws UnsupportedOperationException
	 *             if the list does not support removing elements.
	 */
	protected void removeRange(int fromIndex, int toIndex) {
		ListIterator<E> itr = listIterator(fromIndex);
		for (int index = fromIndex; index < toIndex; index++) {
			itr.next();
			itr.remove();
		}
	}

	/**
	 * Replace an element of this list with another object (optional operation).
	 * This implementation always throws an UnsupportedOperationException.
	 * 
	 * @param index
	 *            the position within this list of the element to be replaced
	 * @param o
	 *            the object to replace it with
	 * @return the object that was replaced
	 * @throws UnsupportedOperationException
	 *             if this list does not support the set operation
	 * @throws IndexOutOfBoundsException
	 *             if index &lt; 0 || index &gt;= size()
	 * @throws ClassCastException
	 *             if o cannot be added to this list due to its type
	 * @throws IllegalArgumentException
	 *             if o cannot be added to this list for some other reason
	 */
	public E set(int index, E o) {
		throw new UnsupportedOperationException();
	}

	/**
	 * Obtain a List view of a subsection of this list, from fromIndex
	 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
	 * sublist is empty. The returned list should be modifiable if and only if
	 * this list is modifiable. Changes to the returned list should be reflected
	 * in this list. If this list is structurally modified in any way other than
	 * through the returned list, the result of any subsequent operations on the
	 * returned list is undefined.
	 * <p>
	 * 
	 * This implementation returns a subclass of AbstractList. It stores, in
	 * private fields, the offset and size of the sublist, and the expected
	 * modCount of the backing list. If the backing list implements
	 * RandomAccess, the sublist will also.
	 * <p>
	 * 
	 * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
	 * <code>add(int, Object)</code>, <code>remove(int)</code>,
	 * <code>addAll(int, Collection)</code> and
	 * <code>removeRange(int, int)</code> methods all delegate to the
	 * corresponding methods on the backing abstract list, after bounds-checking
	 * the index and adjusting for the offset. The
	 * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
	 * The <code>listIterator(int)</code> method returns a "wrapper object" over
	 * a list iterator on the backing list, which is created with the
	 * corresponding method on the backing list. The <code>iterator()</code>
	 * method merely returns listIterator(), and the <code>size()</code> method
	 * merely returns the subclass's size field.
	 * <p>
	 * 
	 * All methods first check to see if the actual modCount of the backing list
	 * is equal to its expected value, and throw a
	 * ConcurrentModificationException if it is not.
	 * 
	 * @param fromIndex
	 *            the index that the returned list should start from (inclusive)
	 * @param toIndex
	 *            the index that the returned list should go to (exclusive)
	 * @return a List backed by a subsection of this list
	 * @throws IndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; size()
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @see ConcurrentModificationException
	 * @see RandomAccess
	 */
	public List<E> subList(int fromIndex, int toIndex) {
		// This follows the specification of AbstractList, but is inconsistent
		// with the one in List. Don't you love Sun's inconsistencies?
		if (fromIndex > toIndex)
			throw new IllegalArgumentException(fromIndex + " > " + toIndex);
		if (fromIndex < 0 || toIndex > size())
			throw new IndexOutOfBoundsException();

		if (this instanceof RandomAccess)
			return new RandomAccessSubList<E>(this, fromIndex, toIndex);
		return new SubList<E>(this, fromIndex, toIndex);
	}

	/**
	 * This class follows the implementation requirements set forth in
	 * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
	 * by using a non-public top-level class in the same package.
	 * 
	 * @author Original author unknown
	 * @author Eric Blake (ebb9@email.byu.edu)
	 */
	private static class SubList<E> extends AbstractList<E> {
		// Package visible, for use by iterator.
		/** The original list. */
		final AbstractList<E> backingList;
		/** The index of the first element of the sublist. */
		final int offset;
		/** The size of the sublist. */
		int size;

		/**
		 * Construct the sublist.
		 * 
		 * @param backing
		 *            the list this comes from
		 * @param fromIndex
		 *            the lower bound, inclusive
		 * @param toIndex
		 *            the upper bound, exclusive
		 */
		SubList(AbstractList<E> backing, int fromIndex, int toIndex) {
			backingList = backing;
			modCount = backing.modCount;
			offset = fromIndex;
			size = toIndex - fromIndex;
		}

		/**
		 * This method checks the two modCount fields to ensure that there has
		 * not been a concurrent modification, returning if all is okay.
		 * 
		 * @throws ConcurrentModificationException
		 *             if the backing list has been modified externally to this
		 *             sublist
		 */
		// This can be inlined. Package visible, for use by iterator.
		void checkMod() {
			if (modCount != backingList.modCount)
				throw new ConcurrentModificationException();
		}

		/**
		 * This method checks that a value is between 0 and size (inclusive). If
		 * it is not, an exception is thrown.
		 * 
		 * @param index
		 *            the value to check
		 * @throws IndexOutOfBoundsException
		 *             if index &lt; 0 || index &gt; size()
		 */
		// This will get inlined, since it is private.
		private void checkBoundsInclusive(int index) {
			if (index < 0 || index > size)
				throw new IndexOutOfBoundsException("Index: " + index
						+ ", Size:" + size);
		}

		/**
		 * This method checks that a value is between 0 (inclusive) and size
		 * (exclusive). If it is not, an exception is thrown.
		 * 
		 * @param index
		 *            the value to check
		 * @throws IndexOutOfBoundsException
		 *             if index &lt; 0 || index &gt;= size()
		 */
		// This will get inlined, since it is private.
		private void checkBoundsExclusive(int index) {
			if (index < 0 || index >= size)
				throw new IndexOutOfBoundsException("Index: " + index
						+ ", Size:" + size);
		}

		/**
		 * Specified by AbstractList.subList to return the private field size.
		 * 
		 * @return the sublist size
		 * @throws ConcurrentModificationException
		 *             if the backing list has been modified externally to this
		 *             sublist
		 */
		public int size() {
			checkMod();
			return size;
		}

		/**
		 * Specified by AbstractList.subList to delegate to the backing list.
		 * 
		 * @param index
		 *            the location to modify
		 * @param o
		 *            the new value
		 * @return the old value
		 * @throws ConcurrentModificationException
		 *             if the backing list has been modified externally to this
		 *             sublist
		 * @throws UnsupportedOperationException
		 *             if the backing list does not support the set operation
		 * @throws IndexOutOfBoundsException
		 *             if index &lt; 0 || index &gt;= size()
		 * @throws ClassCastException
		 *             if o cannot be added to the backing list due to its type
		 * @throws IllegalArgumentException
		 *             if o cannot be added to the backing list for some other
		 *             reason
		 */
		public E set(int index, E o) {
			checkMod();
			checkBoundsExclusive(index);
			return backingList.set(index + offset, o);
		}

		/**
		 * Specified by AbstractList.subList to delegate to the backing list.
		 * 
		 * @param index
		 *            the location to get from
		 * @return the object at that location
		 * @throws ConcurrentModificationException
		 *             if the backing list has been modified externally to this
		 *             sublist
		 * @throws IndexOutOfBoundsException
		 *             if index &lt; 0 || index &gt;= size()
		 */
		public E get(int index) {
			checkMod();
			checkBoundsExclusive(index);
			return backingList.get(index + offset);
		}

		/**
		 * Specified by AbstractList.subList to delegate to the backing list.
		 * 
		 * @param index
		 *            the index to insert at
		 * @param o
		 *            the object to add
		 * @throws ConcurrentModificationException
		 *             if the backing list has been modified externally to this
		 *             sublist
		 * @throws IndexOutOfBoundsException
		 *             if index &lt; 0 || index &gt; size()
		 * @throws UnsupportedOperationException
		 *             if the backing list does not support the add operation.
		 * @throws ClassCastException
		 *             if o cannot be added to the backing list due to its type.
		 * @throws IllegalArgumentException
		 *             if o cannot be added to the backing list for some other
		 *             reason.
		 */
		public void add(int index, E o) {
			checkMod();
			checkBoundsInclusive(index);
			backingList.add(index + offset, o);
			size++;
			modCount = backingList.modCount;
		}

		/**
		 * Specified by AbstractList.subList to delegate to the backing list.
		 * 
		 * @param index
		 *            the index to remove
		 * @return the removed object
		 * @throws ConcurrentModificationException
		 *             if the backing list has been modified externally to this
		 *             sublist
		 * @throws IndexOutOfBoundsException
		 *             if index &lt; 0 || index &gt;= size()
		 * @throws UnsupportedOperationException
		 *             if the backing list does not support the remove operation
		 */
		public E remove(int index) {
			checkMod();
			checkBoundsExclusive(index);
			E o = backingList.remove(index + offset);
			size--;
			modCount = backingList.modCount;
			return o;
		}

		/**
		 * Specified by AbstractList.subList to delegate to the backing list.
		 * This does no bounds checking, as it assumes it will only be called by
		 * trusted code like clear() which has already checked the bounds.
		 * 
		 * @param fromIndex
		 *            the lower bound, inclusive
		 * @param toIndex
		 *            the upper bound, exclusive
		 * @throws ConcurrentModificationException
		 *             if the backing list has been modified externally to this
		 *             sublist
		 * @throws UnsupportedOperationException
		 *             if the backing list does not support removing elements.
		 */
		protected void removeRange(int fromIndex, int toIndex) {
			checkMod();

			backingList.removeRange(offset + fromIndex, offset + toIndex);
			size -= toIndex - fromIndex;
			modCount = backingList.modCount;
		}

		/**
		 * Specified by AbstractList.subList to delegate to the backing list.
		 * 
		 * @param index
		 *            the location to insert at
		 * @param c
		 *            the collection to insert
		 * @return true if this list was modified, in other words, c is
		 *         non-empty
		 * @throws ConcurrentModificationException
		 *             if the backing list has been modified externally to this
		 *             sublist
		 * @throws IndexOutOfBoundsException
		 *             if index &lt; 0 || index &gt; size()
		 * @throws UnsupportedOperationException
		 *             if this list does not support the addAll operation
		 * @throws ClassCastException
		 *             if some element of c cannot be added to this list due to
		 *             its type
		 * @throws IllegalArgumentException
		 *             if some element of c cannot be added to this list for
		 *             some other reason
		 * @throws NullPointerException
		 *             if the specified collection is null
		 */
		public boolean addAll(int index, Collection<? extends E> c) {
			checkMod();
			checkBoundsInclusive(index);
			int csize = c.size();
			boolean result = backingList.addAll(offset + index, c);
			size += csize;
			modCount = backingList.modCount;
			return result;
		}

		/**
		 * Specified by AbstractList.subList to return addAll(size, c).
		 * 
		 * @param c
		 *            the collection to insert
		 * @return true if this list was modified, in other words, c is
		 *         non-empty
		 * @throws ConcurrentModificationException
		 *             if the backing list has been modified externally to this
		 *             sublist
		 * @throws UnsupportedOperationException
		 *             if this list does not support the addAll operation
		 * @throws ClassCastException
		 *             if some element of c cannot be added to this list due to
		 *             its type
		 * @throws IllegalArgumentException
		 *             if some element of c cannot be added to this list for
		 *             some other reason
		 * @throws NullPointerException
		 *             if the specified collection is null
		 */
		public boolean addAll(Collection<? extends E> c) {
			return addAll(size, c);
		}

		/**
		 * Specified by AbstractList.subList to return listIterator().
		 * 
		 * @return an iterator over the sublist
		 */
		public Iterator<E> iterator() {
			return listIterator();
		}

		/**
		 * Specified by AbstractList.subList to return a wrapper around the
		 * backing list's iterator.
		 * 
		 * @param index
		 *            the start location of the iterator
		 * @return a list iterator over the sublist
		 * @throws ConcurrentModificationException
		 *             if the backing list has been modified externally to this
		 *             sublist
		 * @throws IndexOutOfBoundsException
		 *             if the value is out of range
		 */
		public ListIterator<E> listIterator(final int index) {
			checkMod();
			checkBoundsInclusive(index);

			return new ListIterator<E>() {
				private final ListIterator<E> i = backingList
						.listIterator(index + offset);
				private int position = index;

				/**
				 * Tests to see if there are any more objects to return.
				 * 
				 * @return True if the end of the list has not yet been reached.
				 */
				public boolean hasNext() {
					return position < size;
				}

				/**
				 * Tests to see if there are objects prior to the current
				 * position in the list.
				 * 
				 * @return True if objects exist prior to the current position
				 *         of the iterator.
				 */
				public boolean hasPrevious() {
					return position > 0;
				}

				/**
				 * Retrieves the next object from the list.
				 * 
				 * @return The next object.
				 * @throws NoSuchElementException
				 *             if there are no more objects to retrieve.
				 * @throws ConcurrentModificationException
				 *             if the list has been modified elsewhere.
				 */
				public E next() {
					if (position == size)
						throw new NoSuchElementException();
					position++;
					return i.next();
				}

				/**
				 * Retrieves the previous object from the list.
				 * 
				 * @return The next object.
				 * @throws NoSuchElementException
				 *             if there are no previous objects to retrieve.
				 * @throws ConcurrentModificationException
				 *             if the list has been modified elsewhere.
				 */
				public E previous() {
					if (position == 0)
						throw new NoSuchElementException();
					position--;
					return i.previous();
				}

				/**
				 * Returns the index of the next element in the list, which will
				 * be retrieved by <code>next()</code>
				 * 
				 * @return The index of the next element.
				 */
				public int nextIndex() {
					return i.nextIndex() - offset;
				}

				/**
				 * Returns the index of the previous element in the list, which
				 * will be retrieved by <code>previous()</code>
				 * 
				 * @return The index of the previous element.
				 */
				public int previousIndex() {
					return i.previousIndex() - offset;
				}

				/**
				 * Removes the last object retrieved by <code>next()</code> from
				 * the list, if the list supports object removal.
				 * 
				 * @throws IllegalStateException
				 *             if the iterator is positioned before the start of
				 *             the list or the last object has already been
				 *             removed.
				 * @throws UnsupportedOperationException
				 *             if the list does not support removing elements.
				 */
				public void remove() {
					i.remove();
					size--;
					position = nextIndex();
					modCount = backingList.modCount;
				}

				/**
				 * Replaces the last object retrieved by <code>next()</code> or
				 * <code>previous</code> with o, if the list supports object
				 * replacement and an add or remove operation has not already
				 * been performed.
				 * 
				 * @throws IllegalStateException
				 *             if the iterator is positioned before the start of
				 *             the list or the last object has already been
				 *             removed.
				 * @throws UnsupportedOperationException
				 *             if the list doesn't support the addition or
				 *             removal of elements.
				 * @throws ClassCastException
				 *             if the type of o is not a valid type for this
				 *             list.
				 * @throws IllegalArgumentException
				 *             if something else related to o prevents its
				 *             addition.
				 * @throws ConcurrentModificationException
				 *             if the list has been modified elsewhere.
				 */
				public void set(E o) {
					i.set(o);
				}

				/**
				 * Adds the supplied object before the element that would be
				 * returned by a call to <code>next()</code>, if the list
				 * supports addition.
				 * 
				 * @param o
				 *            The object to add to the list.
				 * @throws UnsupportedOperationException
				 *             if the list doesn't support the addition of new
				 *             elements.
				 * @throws ClassCastException
				 *             if the type of o is not a valid type for this
				 *             list.
				 * @throws IllegalArgumentException
				 *             if something else related to o prevents its
				 *             addition.
				 * @throws ConcurrentModificationException
				 *             if the list has been modified elsewhere.
				 */
				public void add(E o) {
					i.add(o);
					size++;
					position++;
					modCount = backingList.modCount;
				}

				// Here is the reason why the various modCount fields are mostly
				// ignored in this wrapper listIterator.
				// If the backing listIterator is failfast, then the following
				// holds:
				// Using any other method on this list will call a corresponding
				// method on the backing list *after* the backing listIterator
				// is created, which will in turn cause a ConcurrentModException
				// when this listIterator comes to use the backing one. So it is
				// implicitly failfast.
				// If the backing listIterator is NOT failfast, then the whole
				// of
				// this list isn't failfast, because the modCount field of the
				// backing list is not valid. It would still be *possible* to
				// make the iterator failfast wrt modifications of the sublist
				// only, but somewhat pointless when the list can be changed
				// under
				// us.
				// Either way, no explicit handling of modCount is needed.
				// However modCount = backingList.modCount must be executed in
				// add
				// and remove, and size must also be updated in these two
				// methods,
				// since they do not go through the corresponding methods of the
				// subList.
			};
		}
	} // class SubList

	/**
	 * This class is a RandomAccess version of SubList, as required by
	 * {@link AbstractList#subList(int, int)}.
	 * 
	 * @author Eric Blake (ebb9@email.byu.edu)
	 */
	private static final class RandomAccessSubList<E> extends SubList<E>
			implements RandomAccess {
		/**
		 * Construct the sublist.
		 * 
		 * @param backing
		 *            the list this comes from
		 * @param fromIndex
		 *            the lower bound, inclusive
		 * @param toIndex
		 *            the upper bound, exclusive
		 */
		RandomAccessSubList(AbstractList<E> backing, int fromIndex, int toIndex) {
			super(backing, fromIndex, toIndex);
		}
	} // class RandomAccessSubList

} // class AbstractList
